package leetcode_day._2022._202203._2131;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/21 20:17
 * 两数之和 IV - 输入 BST
 * 算法：哈希表、双指针 + 二叉树
 */
public class _21_653 {

    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) break;
            root = stack.pop();
            if (set.contains(k - root.val)) return true;
            set.add(root.val);
            root = root.right;
        }
        return false;
    }

    /**
     * 因为二叉树是二叉搜索树，所以是有顺序的，左子树小于右子树
     * @param root root
     * @param k k
     * @return true or false
     */
    public boolean findTarget_better(TreeNode root, int k) {
        Deque<TreeNode> ls = new ArrayDeque<>(), rs = new ArrayDeque<>();
        TreeNode tmp = root;
        while (tmp != null) {
            ls.addLast(tmp);
            tmp = tmp.left;
        }
        tmp = root;
        while (tmp != null) {
            rs.addLast(tmp);
            tmp = tmp.right;
        }
        TreeNode l = ls.peekLast(), r = rs.peekLast();
        // 如果没有找到，那么最终都会将根节点弹出，这样 l.val == r.val, 题目保证了至少有一个节点
        while (l.val < r.val) {
            int t = l.val + r.val;
            if (t == k) return true;
            if (t < k) l = getNext(ls, true);
            else r = getNext(rs, false);
        }
        return false;
    }
    private TreeNode getNext(Deque<TreeNode> d, boolean isLeft) {
        TreeNode node = isLeft ? d.pollLast().right : d.pollLast().left;
        while (node != null) {
            d.addLast(node);
            node = isLeft ? node.left : node.right;
        }
        return d.peekLast();
    }

}
